954D - Fight Against Traffic - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define fi first
#define se second
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define pb push_back
#define yes {cout<<"Yes"<<endl;return;}
#define no {cout<<"No"<<endl;return;}
#define cntbit __builtin_popcountll
#define pii pair<int,int>
#define vii vector<pair<int,int>>
#define all(x) (x).begin(), (x).end()
using namespace std;
const int N = 1010;
const int inf = 1e18;
const int mod = 1e9+7;
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int qmi(int a,int b){
	int res=1;
	for(;b;b>>=1){
		if(b&1) res=res*a%mod;
		a=a*a%mod; 
	}return res;
}
int n,m,s,t; vector<int> e[N];
vector<vector<int>> dis;
void bfs(int s){
	dis[s][s]=0;
	queue<int> q;
	q.push(s);
	while(q.size()){
		int u=q.front();
		q.pop();
		for(auto v:e[u]){
			if(dis[s][v]>dis[s][u]+1){
				q.push(v);
				dis[s][v]=dis[s][u]+1;
			}
		}
	}
}
int edge[N][N];
void solve(){
	cin>>n>>m>>s>>t;
	dis=vector<vector<int>> (n+1,vector<int> (n+1,inf));
	int ans=0;
	while(m--){
		int u,v;cin>>u>>v;
		e[u].pb(v);
		e[v].pb(u);
		edge[u][v]=1;
		edge[v][u]=1;
	}
	rep(i,1,n+1) bfs(i);
	rep(i,1,n+1) rep(j,i+1,n+1){//won't dec
		if(edge[i][j]) continue;
		int cond1=((dis[s][i]+1+dis[j][t])>=dis[s][t]);
		int cond2=((dis[s][j]+1+dis[i][t])>=dis[s][t]);
		cond1&=cond2;
		if(cond1) ans++;
	}
	cout<<ans<<endl;
	
	
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	cout<<fixed<<setprecision(12);
	int task=1;//cin>>task;
	rep(i,0,task){
		solve();
	}
}